import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    public class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    //创建二叉树,返回根节点
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        return A;
    }
    //进行树的遍历
    //1-1.前序遍历:不带返回类型
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //1-2-1.前序遍历：带返回值类型
    List<Character> ret = new ArrayList<>();
    public List<Character> preorderTraversal1(TreeNode root){
        if (root == null){
            return ret;
        }
        ret.add(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);
        return ret;
    }
    //1-2-1.前序遍历：带返回值类型
    public List<Character> preorderTraversal2(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }
        ret.add(root.val);
        List<Character> left = preorderTraversal2(root.left);
        ret.addAll(left);
        List<Character> right = preorderTraversal2(root.right);
        ret.addAll(right);
        return ret;
    }
    //2.中序遍 历：带返回值类型
    public List<Character> inorderTraversal(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }
        List<Character> left = inorderTraversal(root.left);
        ret.addAll(left);
        ret.add(root.val);
        List<Character> right = inorderTraversal(root.right);
        ret.addAll(right);
        return ret;
    }
    //3.后序遍 历：带返回值类型
    public List<Character> postorderTraversal(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }
        List<Character> left = postorderTraversal(root.left);
        ret.addAll(left);
        List<Character> right = postorderTraversal(root.right);
        ret.addAll(right);
        ret.add(root.val);
        return ret;
    }
    //方法1：计算叶子节点的数量-当root的左节点和右节点都为0的时候，叶子节点的数量加1
    public int leafCount = 0;
    public int getLeafNodeCount1(TreeNode root){
        if (root == null){
            return 0;
        }else if (root.left == null && root.right == null){
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
        return leafCount;
    }
    //方法2：计算叶子节点的数量-叶子节点的数量等于左子树的叶子节点数量+右子树的叶子节点的数量
    public int getLeafNodeCount2(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }
    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root == null){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度:整棵树的高度等于左树和右树高度的最大值+1（因为有该节点本身）
    public int getHeight1(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(getHeight1(root.left),getHeight1(root.right))+1;
    }
    public int getHeight2(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHigh = getHeight2(root.left);
        int rightHigh = getHeight2(root.right);
        return (leftHigh > rightHigh ? leftHigh:rightHigh) + 1;
    }
    // 检测值为value的元素是否存在:需要对二叉树进行遍历，可以使用前序遍历
    public TreeNode find(TreeNode root, char val){
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        TreeNode left = find(root.left,val);
        if (left!=null){
            return left;
        }
        TreeNode right = find(root.right,val);
        if (right!=null){
            return right;
        }
        return null;
    }
    //层序遍历
    public void levelOrder(TreeNode root){

    }
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        return false;
    }

    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //有null的情况
        if (p == null && q != null || p != null && q == null){
            return false;
        }
        if (p == null && q == null){
            return true;
        }
        //当不是null时，两个节点的值必须相等，否则两棵树不一样
        if (p.val != q.val){
            return false;
        }
        //此时当前遇到的节点的值一样，继续往下遍历
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //给你两棵二叉树 root 和 subRoot 。
    // 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
    // 如果存在，返回 true ；否则，返回 false
    //1.判断root和subroot是不是两颗相同的树：isSameTree
    //2.判断这棵树是不是root左树的子树
    //3.判断这棵树是不是root右树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    //给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    public TreeNode invertTree(TreeNode root) {
        TreeNode root_1 = root;
        if (root == null) {
            return null;
        }
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        invertTree(root.left);
        invertTree(root.right);
        return root_1;
    }
    //给定一个二叉树，判断它是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        int leftHigh = getHeight3(root.left);
        int rightHigh = getHeight3(root.right);
        if (Math.abs(leftHigh - rightHigh) >= 2){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    // 获取二叉树的高度:整棵树的高度等于左树和右树高度的最大值+1（因为有该节点本身）
    public int getHeight3(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(getHeight3(root.left),getHeight3(root.right))+1;
    }


}
